home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / tex / egrep.zip / EGREP.C < prev    next >
C/C++ Source or Header  |  1988-03-31  |  12KB  |  451 lines
  1. /*
  2.      Boyer/Moore/Gosper-assisted 'egrep' search, with delta0 table as in
  3.      original paper (CACM, October, 1977).  No delta1 or delta2.  According to
  4.      experiment (Horspool, Soft. Prac. Exp., 1982), delta2 is of minimal
  5.      practical value.  However, to improve for worst case input, integrating
  6.      the improved Galil strategies (Apostolico/Giancarlo, Siam. J. Comput.,
  7.      February 1986) deserves consideration.
  8.  
  9.      Method:     extract longest metacharacter-free string from expression.
  10.         this is done using a side-effect from henry spencer's regcomp().
  11.         use boyer-moore to match such, then pass submatching lines
  12.         to rexexp() for short input, or standard 'egrep' for long
  13.         input.  (this tradeoff is due to the general slowness of the
  14.         regexp() nondeterministic machine on complex expressions,
  15.         as well as the startup time of 'egrep' on short files.)
  16.         alternatively, you may change the faster 'egrep' automaton
  17.         to include boyer-moore directly.
  18.      Future: 
  19.              beef up for multiple patterns ala bm/fgrep.  can do fast -n 
  20.         via file rescan, but it's a luxury.  adapt 'fastfind'.
  21.         internationalize for kanji.
  22.  
  23.      James A. Woods                    Copyright (c) 1986
  24.      NASA Ames Research Center
  25. */
  26. #ifdef    V7
  27. #define BSD
  28. #define void    int
  29. #endif
  30.  
  31. #include <stdio.h>
  32. #include <ctype.h>
  33. #include <sys/types.h>
  34. #include <sys/stat.h>
  35. #include <regexp.h>        /* must be henry spencer's version */
  36.  
  37. #ifdef    BSD
  38. #define    strchr    index
  39. #endif
  40. #ifndef EGREP
  41. #define    EGREP    "/bin/local/egrep"  /* prevent installation-dependent recursion */
  42. #endif
  43. #define BUFSIZE    8192
  44. #define PATSIZE 1000
  45. #define LARGE     BUFSIZE + PATSIZE
  46. #define FSIZE    50000        /* algorithm tradeoff at this length (ad hoc) */
  47. #define NL    '\n'
  48. #define    EOS    '\0'
  49.  
  50. extern char *optarg;
  51. extern int optind;
  52.  
  53. int cflag, iflag, eflag, fflag, lflag;
  54. int boyflag, rxflag;
  55. int hflag;
  56. int nfile, nsuccess;
  57. long nmatch;
  58.  
  59. regexp *rspencer;
  60. char *pattern, *patboy;
  61. int delta0[256];        /* ascii only -- see note at gosper() */
  62. char cmap[256];            /* (un)folded characters */
  63. char str[BUFSIZE+2];
  64. char linetemp[BUFSIZE];
  65. char grepcmd[PATSIZE]; 
  66.  
  67. struct stat stbuf;
  68. int fd;
  69. FILE *egout, *mcilroy(), *popen();
  70. char *strchr(), *strcpy(), *strncpy(), *strpbrk(), *malloc();
  71. char *fold(), *sys5fold();
  72.  
  73. main ( argc, argv )
  74.     int argc; char *argv[];
  75. {
  76.         int c;
  77.         int errflag = 0;
  78.         int oldegrep = 0;
  79.  
  80.         while ( (c = getopt ( argc, argv, "bchie:f:lnv" ) ) != EOF )
  81.  
  82.                 switch(c) {
  83.  
  84.         case 'f':
  85.             fflag++;
  86.                 case 'b':
  87.         case 'n':
  88.         case 'v':
  89.             oldegrep++;    /* boyer-moore of little help here */
  90.                         continue;
  91.                 case 'c':
  92.                         cflag++;
  93.                         continue;
  94.                 case 'e':
  95.                         eflag++;
  96.                         pattern = optarg;
  97.                         continue;
  98.         case 'h':
  99.             hflag++;    /* shh ... for newshounds */
  100.             continue;
  101.                 case 'i':
  102.                         iflag++;
  103.                         continue;
  104.                 case 'l':
  105.                         lflag++;
  106.                         continue;
  107.                 case '?':
  108.                         errflag++;
  109.             }
  110.         argc -= optind;
  111.         if ( errflag || ((argc <= 0) && !fflag) )
  112.         oops ( "usage: egrep [-bcilnv] [-e exp] [-f file] [strings] [file]" );
  113.         if ( !eflag ) {
  114.                 pattern = argv[optind++];
  115.                 argc--;
  116.         }
  117.     if ( oldegrep || (strchr ( pattern, '\n' ) != NULL) ) {
  118.         execvp ( EGREP, argv );
  119.         oops ( "can't exec old 'egrep'" );
  120.     }
  121.         if ( iflag ) {
  122.         strcpy ( pattern, fold ( pattern ) );
  123.     }
  124.     if ( strpbrk ( pattern, "^$.[]()?+*|\\" ) == NULL ) {    /* do boyer-moore only */
  125.         boyflag++;
  126.         rxflag = 0;
  127.         patboy = pattern;
  128.     }
  129.     else {     
  130.         /*
  131.             first compile a fake regexp to isolate longest
  132.             metacharacter-free string
  133.         */
  134.         {
  135.             char *dummyp;
  136.             dummyp = malloc ( (unsigned) strlen ( pattern ) + 5 );
  137.             sprintf ( dummyp, "(.)*%s", pattern );
  138.             rspencer = regcomp ( dummyp );
  139.         }
  140.         if ( rspencer -> regmust == NULL ) {        /* pattern too complicated */
  141.             execvp ( EGREP, argv );
  142.             oops ( "can't exec old 'egrep'" );
  143.         }
  144.         patboy = rspencer -> regmust;
  145.         if ( (rspencer = regcomp ( pattern )) == NULL )
  146.             oops ( "egrep: regcomp failure" );
  147.     }
  148.     gosper ( patboy );
  149.         argv = &argv[optind];
  150.         nfile = argc;
  151.         if ( argc <= 0 ) {        /* process stdin */
  152.                 if ( lflag )
  153.             exit ( 1 );
  154.         fd = 0;
  155.         if ( !boyflag )
  156.             if ( (egout = mcilroy ( (char *) NULL )) == NULL )
  157.                 oops ( "egrep: no processes" );
  158.                 boyermoore ( (char *) NULL, patboy );
  159.         if ( !boyflag )
  160.             pclose ( egout );
  161.         }
  162.         else {
  163.                 while ( --argc >= 0 ) {
  164.                     if ( (fd = open ( *argv, 0 )) <= 0 ) {
  165.                             fprintf ( stderr, "egrep: can't open %s\n", *argv );
  166.                             nsuccess = 2;
  167.                 argv++;
  168.                 continue;
  169.             }
  170.             if ( !boyflag ) {
  171.                 fstat ( fd, &stbuf );
  172.                 if ( stbuf.st_size < FSIZE )
  173.                     rxflag = 1;
  174.                 else {
  175.                     rxflag = 0;
  176.                     if ( (egout = mcilroy ( *argv )) == NULL )
  177.                         oops ( "egrep: no processes" );
  178.                 }
  179.             }
  180.                         boyermoore ( *argv, patboy );
  181.             if ( !boyflag && !rxflag ) {
  182.                 fflush ( egout );
  183.                 pclose ( egout );
  184.             }
  185.             close ( fd );
  186.             argv++;
  187.                 }
  188.     }
  189.         exit ( (nsuccess == 2) ? 2 : (nsuccess == 0) );
  190. }
  191.  
  192. boyermoore ( file, pattern )    /* "reach out and boyer-moore search someone" */
  193.     char *file, *pattern;    /* -- soon-to-be-popular bumper sticker */
  194. {
  195.     register char *k, *strend, *s;
  196.     register int j;
  197.     int patlen;
  198.     char *t;
  199.     char *gotamatch();
  200.     int nleftover, count;
  201.  
  202.     patlen = strlen ( pattern );
  203.     nleftover = nmatch = 0;
  204.  
  205. #ifdef V7
  206. #define read xread
  207. #endif
  208.     while ( (count = read ( fd, str + nleftover, BUFSIZE - nleftover )) > 0 ) {
  209.  
  210. #undef read
  211.         count += nleftover;
  212.         if ( count != BUFSIZE && fd != 0)
  213.             str[count++] = NL;    /* insurance for broken last line */
  214.         str[count] = 0;
  215.         for ( j = count - 1; str[j] != NL && j >= 0; )
  216.             j--;
  217.         if ( j < 0 ) {            /* break up long line */
  218.             str[count] = NL;
  219.             str[++count] = EOS;
  220.             strend = str + count;
  221.             linetemp[0] = EOS;
  222.             nleftover = 0;
  223.         }
  224.         else {                /* save partial line */
  225.             strend = str + j;
  226.             nleftover = count - j - 1;
  227.             strncpy ( linetemp, str + j + 1, nleftover );
  228.         }
  229.         k = str + patlen - 1;
  230.  
  231.         for ( ; ; ) {
  232.             /*
  233.                 for a large class of patterns, upwards of 80% of 
  234.                 match time is spent on the next line.  
  235.                 we beat existing microcode (vax 'matchc') this way.
  236.             */
  237. #ifndef V7
  238.             while ( (k += delta0[*(unsigned char *)k]) < strend )
  239.                 ;    
  240. #else
  241.             while ( (k += delta0[*(char *)k & 0377]) < strend )
  242.                 ;
  243. #endif
  244.             if ( k < (str + LARGE) )
  245.                 break;
  246.             k -= LARGE;
  247.  
  248.             j = patlen - 1;
  249.             s = k - 1;
  250.             while ( cmap[*s--] == pattern[--j] )
  251.                 ;
  252.             /*
  253.                 delta-less shortcut for literati, but 
  254.                 short shrift for genetic engineers.
  255.             */
  256.             if ( j >= 0 )
  257.                 k++;
  258.             else {            /* submatch */
  259.                 t = k;
  260.                 s = k - patlen + 1;
  261.                 do 
  262.                     ;
  263.                 while ( *s != NL && --s >= str ); 
  264.                 k = s + 1;    /* at line start */
  265.  
  266.                 if ( boyflag ) {
  267.                     if ( (k = gotamatch ( file, k )) == NULL )
  268.                         return;
  269.                 }
  270.                 else if ( !rxflag ) {    /* fob off to egrep */
  271.                     do
  272.                         putc ( *k, egout );
  273.                     while ( *k++ != NL );
  274.                 }
  275.                 else {                /* regexec() wants EOS */
  276.                     s = t;
  277.                     do
  278.                         ;
  279.                     while ( *s++ != NL );
  280.                     *--s = EOS;
  281.  
  282.                     if ( regexec ( rspencer, ((iflag) ? fold ( k ) : k) ) == 1 ) {
  283.                         *s = NL;
  284.                         if ( gotamatch ( file, k ) == NULL )
  285.                             return;
  286.                     }
  287.                     *s = NL;
  288.                     k = s + 1;
  289.                 }
  290.                 if ( k >= strend )
  291.                     break;
  292.             }
  293.         }
  294.         strncpy ( str, linetemp, nleftover );
  295.     }
  296.     if ( cflag && (boyflag || rxflag) ) {
  297.         if ( nfile > 1 )
  298.             printf ( "%s:", file );
  299.         printf ( "%ld\n", nmatch );
  300.     }
  301. }
  302.  
  303. FILE *
  304. mcilroy ( file )    /* open a pipe to old 'egrep' for long files, */
  305.     char *file;    /* ... where rege